<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>JS 二分查找</title>
</head>
<body>
    <p>二分查找</p>

    <script>
        /**
         * 二分查找（循环）
         * @param arr 数组
         * @param target 目标值
         * @returns index
         */
        function binarySearch1(arr, target) {
            const length = arr.length
            if (length === 0) return -1

            let startIndex = 0 // 开始位置
            let endIndex = length - 1 // 结束位置

            while (startIndex <= endIndex) {
                const midIndex = Math.floor((startIndex + endIndex) / 2) // 中间位置
                const midValue = arr[midIndex]
                if (target < midValue) {
                    // 目标值较小，则继续在左侧查找
                    endIndex = midIndex - 1
                } else if (target > midValue) {
                    // 目标值较大，则继续在右侧查找
                    startIndex = midIndex + 1
                } else {
                    // 相等，则返回
                    return midIndex
                }
            }

            return -1 // 未找到
        }

        /**
         * 二叉查找（递归）
         * @param arr 数组
         * @param target 目标值
         * @param startIndex startIndex
         * @param endIndex endIndex
         */
        function binarySearch2(arr, target, startIndex, endIndex) {
            const length = arr.length
            if (length === 0) return -1

            // 开始和结束的范围
            if (startIndex == null) startIndex = 0
            if (endIndex == null) endIndex = length - 1

            // 开始和结束相遇，则结束
            if (startIndex === endIndex) return -1

            // 中间位置
            const midIndex = Math.floor((startIndex + endIndex) / 2)
            const midValue = arr[midIndex]

            if (target < midValue) {
                // 目标值较小，则从左侧寻找
                return binarySearch2(arr, target, startIndex, midIndex - 1)
            } else if (target > midValue) {
                // 目标值较大，则从右侧查找
                return binarySearch2(arr, target, midIndex + 1, endIndex)
            } else {
                // 相等，则返回
                return midIndex
            }
        }

        // 功能测试
        const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        const target = 2
        console.log(binarySearch1(arr, target))
        console.log(binarySearch2(arr, target))
    </script>
</body>
</html>